// ConvertSortedArray2BST.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
using namespace std;
/**
 * Definition for binary tree*/
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int>& num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(num.size() <=0) return NULL;
        if(num.size() == 1){
            TreeNode* root = new TreeNode(num[0]);
            return root;
        }
        
        TreeNode* root = Help(num, 0, num.size()-1);
        
        return root;
    }
    
    TreeNode* Help(vector<int>& num, int start, int end)
    {
        if(end < start) return NULL;
		if(end==start)
		{
			TreeNode* root = new TreeNode(num[start]);
			return root;
		}
        int mid = start + (end-start)/2;
        TreeNode* root = new TreeNode(num[mid]);
        
        TreeNode* L = Help(num, start, mid-1);
        TreeNode* R = Help(num, mid+1, end);
        root->left =L;
        root->right =R;
        return root;
    }
};
int _tmain(int argc, _TCHAR* argv[])
{
	Solution S;
	vector<int> num;
	for(int i = 1; i<=7; i++)
		num.push_back(i);
	S.sortedArrayToBST(num);
	return 0;
}

